// sgu372
// 题意：
// 现在有k(<=1000)个人进行茶会，有n(<=1000)种茶，可能是红茶或者绿茶，
// 现在你要举行k轮茶会，每一轮要用不同的茶，然后不允许连续三轮是红茶
// 或者绿茶，每个种类的茶每包都有一个已知的费用，每一轮你要给每个人都
// 发一包你选中的茶，一轮结束后有个人会因为有事离开。
// 请输出一种费用最小的选茶的方案，如果不可能输出"Impossible"。
//
// 题解：
// 红茶和绿茶都按费用从小到大排序，这样就可以进行dp了，只要保存这一次和
// 前一次是不是绿茶或者红茶对应的最小费用，即f[i][j][st]，表示进行i轮，
// 有j包红茶，这次选择的和上次选择的红绿茶信息。有了这些就可以维护出来。
//
// 然后因为要输出方案，记录一下转移就行。
//
// ml:run = $bin < input
// ml:ccf += -g
// ml:opt = 0
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

struct data { int cost, type, id; };
bool operator<(data const& a, data const& b) { return a.cost < b.cost; }

using ll = long long;
ll  const  inf = (1ll) << 44;
int const maxn = 1007;
std::vector<data> color[2];
int n, k;
ll f[maxn][maxn][4];
int from[maxn][maxn][4];

void fail()
{
    std::cout << "Impossible\n";
    exit(0);
}

template <class T>
bool get_min(T & a, T b)
{
    if (b < a) { a = b; return true; }
    return false;
}

void print(int k, int tj, int tst)
{
    std::stack<int> ans;
    for (int i = k; i >= 1; i--) {
        int t = from[i][tj][tst];
        ans.push(t & 1);
        tst = (tst >> 1) ^ (t & 2);
        if (t & 1) tj--;
    }
    int c[2] = {0, 0};
    for (; !ans.empty(); ans.pop()) {
        int now = ans.top();
        std::cout << color[now][c[now]++].id << " ";
    }
    std::cout << "\n";
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin >> k >> n;
    data tmp;
    for (int i = 0; i < n; i++) {
        std::cin >> tmp.cost >> tmp.type;
        tmp.id = i + 1;
        color[tmp.type].push_back(tmp);
    }
    std::sort(color[0].begin(), color[0].end());
    std::sort(color[1].begin(), color[1].end());

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            for (int st = 0; st < 8; st++) f[i][j][st] = inf;

    for (int st = 0; st < 4; st++) f[0][0][st] = 0;

    for (int i = 1; i <= k; i++) {
        ll re = k - i + 1;
        for (int st = 0; st < 4; st++) {
            int llast = (st >> 1) & 1, last = st & 1;
            // choose j = 0
            if (st != 0 && i <= (int)color[0].size()) {
                if (get_min(f[i][0][((st & 1) << 1) ^ 0], f[i - 1][0][st] + color[0][i - 1].cost * re))
                    from[i][0][((st & 1) << 1) ^ 0] = (llast << 1) ^ 0;
            }
            for (int j = 1; j <= std::min((int)color[1].size(), i); j++) {
                if (i - j > (int)color[0].size()) continue;
                int ti = i - j - 1, tj = j - 1;
                if (j == i) {
                    if (st != 3)
                        if (get_min(f[i][j][(last << 1) ^ 1], f[i - 1][j - 1][st] + color[1][tj].cost * re))
                            from[i][j][(last << 1) ^ 1] = (llast << 1) ^ 1;
                    continue;
                }
                if (last == llast) {
                    if (last == 1) {
                        if (get_min(f[i][j][st ^ 1], f[i - 1][j][st] + color[0][ti].cost * re))
                            from[i][j][st ^ 1] = (llast << 1) ^ 0;
                    } else {
                        if (get_min(f[i][j][st ^ 1], f[i - 1][j - 1][st] + color[1][tj].cost * re))
                            from[i][j][st ^ 1] = (llast << 1) ^ 1;
                    }
                } else {
                    if (get_min(f[i][j][(last << 1) ^ 0], f[i - 1][j][st] + color[0][ti].cost * re))
                        from[i][j][(last << 1) ^ 0] = (llast << 1) ^ 0;
                    if (get_min(f[i][j][(last << 1) ^ 1], f[i - 1][j - 1][st] + color[1][tj].cost * re))
                        from[i][j][(last << 1) ^ 1] = (llast << 1) ^ 1;
                }
            }
        }
    }

    ll ans = inf;
    int tst = 0, tj = 0;
    for (int st = 0; st < 4; st++)
        for (int j = 0; j <= std::min(k, (int)color[1].size()); j++) {
            if (f[k][j][st] < ans) {
                ans = f[k][j][st];
                tj = j;
                tst = st;
            }
        }

    if (ans >= inf) fail();
    else print(k, tj, tst);
}

